KMP 알고리즘이란?
문자열 A 안에 문자열 B가 들어있는지를 판단하는 알고리즘.
즉, 불일치가 발생하기 직전까지 같았던 부분은 다시 비교하지 않고 패턴 매칭을 진행하자는 것이다. 이를 통해 비교 횟수를 줄이고, 검색 알고리즘의 효율성을 높일 수 있다.
실패 함수 F(x)
문자열 S[0:x + 1] 에서 접두사와 접미사가 일치하는 최대 길이
실패 함수의 값은 접두사와 접미사가 일치하는 최대 길이를 의미하지만, 동시에 인덱스 관점에서 ==아직 확신할 수 없는== 다음 문자를 의미하기도 한다. (길이 = 인덱스 + 1)
실패 함수는 다음과 같은 과정으로 이해할 수 있다. (0-index 이다.)
미래의 나에게 도움이 되기를 바라며...
코드
def make_fail_function(s):
f = [0] * len(s)
j = 0
for i in range(1, len(s)):
while j > 0 and s[i] != s[j]:
j = f[j-1]
if s[i] == s[j]: # i 와 j 가 가리키는 글자가 같은지 확인한다.
j += 1 # s[i]와 s[j] 가 같아지는 시점에서 f[j-1] 의 값 + 1
# f[j-1] 이란 s[0:j] 의 접두사와 접미사가 일치하는 최대 길이
f[i] = j # f[i]에 일치하는 최대 길이를 저장한다.
return fKMP 알고리즘
실패 함수를 응용하면 KMP 알고리즘을 구현할 수 있다!!
def kmp(failure, a, b):
count = [0] * len(a)
result = []
j = 0 # j 는 b 를 가리키는 인덱스임과 동시에 일치하는 최대 길이가 된다.
for i in range(len(a)): # 모든 a 안의 index i 를 돌면서
if a[i] == b[j]: # 서로 같을 때
j += 1
count[i] = j # count[i]에 일치하는 최대 길이인 j 를 저장한다.
else:
while j > 0 and a[i] != b[j]: # 만약 a[i] 와 b[i] 가 같지 않다면 실패함수를 이용해서 계속해서 접두사와 접미사를 이동시킨다.
j = failure[j - 1]
# 이 시점에서 j 가 0이거나, a[i] 와 b[j] 가 같게 된다.
if a[i] == b[j]: # 그 중 a[i] 와 b[j] 가 같은 경우는 마찬가지로 최대 길이를 저장해준다.
j += 1
count[i] = j
if count[i] == len(b): # 만약 b 를 끝까지 비교했는데 모두 같다면
result.append(i - len(b) + 2) # (선택) 같은 인덱스를 저장한다. (이때는 1-index 사용해서 +2를 해주었다. 취향 차이.)
j = failure[j - 1] # 바로 이전 문자의 접두사를 끌어온다.
# 명심할 것. j 는 언제나 *다음 비교에서 실패할 수도 있는 b의 인덱스* 이다.
return resultcount 배열은 i에서 최대로 일치하는 문자열의 길이가 담겨있다.
즉, len(b) 가 count 에서 몇 번 나타나는지 알면 문자열이 최대 몇 개가 일치하는지 알 수 있는 것이다.
실패 함수의 성질
반복되는 문자열의 길이 L 은 문자열 길이 - failure[문자열 길이-1] 로 구할 수 있다
failure[문자열 길이 - 1] 은 맨 끝 문자까지의 부분 문자열에서 접두사이자 접미사인 최장 부분 문자열의 길이를 나타낸다.
근데 증명은 못하겠다… 너무 어려워요 나중에 이해되면 추가해보겠습니다.
백준 1305 번에서 사용됩니다
시간 복잡도
시간 복잡도는 이다.